//
//  Problem222.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/6.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 222. 完全二叉树的节点个数
 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

 示例 1：
     输入：root = [1,2,3,4,5,6]
     输出：6
 示例 2：
     输入：root = []
     输出：0
 示例 3：
     输入：root = [1]
     输出：1

 提示：

     树中节点的数目范围是[0, 5 * 104]
     0 <= Node.val <= 5 * 104
     题目数据保证输入的树是 完全二叉树
    进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
 */
@objcMembers class Problem222: NSObject {
    func solution() {
        let rootNode = TreeNode(1)
        rootNode.left = TreeNode(2)
        rootNode.left?.left = TreeNode(4)
        rootNode.left?.right = TreeNode(5)
        rootNode.right = TreeNode(3)
        rootNode.right?.left = TreeNode(6)
        print(countNodesDiGui(rootNode))
    }
    
    /*
     简单的递归
     */
    func countNodes(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        
        return countNodes(root?.left) + countNodes(root?.right) + 1
    }
    
    /*
                1
              /   \
             2     3
            / \   /
           4  5  6
     层级的概念
     第一层全满时的个数 2的0次方  1， 总节点个数是：2的1次方 - 1
     第二层全满时的个数 2的1次方  2， 总节点个数是：2的2次方 - 1
     第三层全满时的个数 2的2次方  4， 总节点个数是：2的2次方 - 1
     所以：假如他有3层，那么最后一层至少1，对多4个，他的编号数组是：[4...7]
     1: 首先确定当前的树有几层，可以根据root的left个数来确定
     2: 知道第几层后，假如有n层，也就是知道了最后一层至少1个，最多 2的n-1次方 [2(n-1) - 1...2(n)]
     下一步确定最后一层有几个数字，使用二分法来确定，看看中间mid是否在树中？
     
     位方法 来确定：
     按照例子，最后一个数字是6，他的二进制是110，他的每一位都是有意义的
     第一位永远是1，因为根节点是1，以后的每位代表：1:代表右侧 0:代表左侧
     那么我们需要知道，给定一个数字n，转换成二进制，然后根据上面的方法，依次验证是否在树中
     
     二分法 来快速判断
     */
    func countNodesWEer(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        
        // 1: 判断有多少层
        var cn = 0
        var troot = root
        while troot != nil {
            cn += 1
            troot = troot?.left
        }
        
        // 2: 根据层数推导出数据的起始位置和结束位置
        var l = 1 << (cn - 1)
        var r = (1 << cn) - 1
        
        
        // 3: 使用二分法，获取mid， 这里+1防治
        var mid = l + (r - l) >> 1
        
        while l <= r {
            // 4: 使用位运算，来判断mid是否在tree中
            var midC = 1 << (cn-2)        // 第一位不需要
            
            var troot = root
            while troot != nil, midC > 0 {
                if midC & mid == 0 {
                    troot = troot?.left
                } else {
                    troot = troot?.right
                }
                midC >>= 1
            }
            
            if troot != nil {   // mid 在树中
                l = mid + 1
            } else {
                r = mid - 1
            }
            
            mid = l + (r - l) >> 1
        }

        return mid
    }
    
    /*
     依然使用层级的概念，
     根据上面的例子：我们有3行，我们知道：最后一行可能没有满，
     那么我们判断一下：根节点的left和right，看看哪个是满的
     有2种情况：
     left满，right不满
         1
       /   \
      2     3
     / \   /
    4  5  6
     left不满，right满
         1
       /   \
      2     3
     /
    4
     假如：满的情况：可以根据层级的公式求出，不满的情况：递归即可
     如何判断是否是哪种情况：根据以right为根，统计层级，是否 = 总层级-1
     */
    func countNodesDiGui(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        // 总层级
        let allN = getCeng(root)
        // 右侧的层级
        let rightN = getCeng(root?.right)
        if allN == rightN + 1 {     // left满，right不满
            // 左 + 右 + 根（1）
            return (1 << (allN - 1)) - 1 + countNodesDiGui(root?.right) + 1
        } else {                    // left不满，right满
            // 左 + 右 + 根（1）
            return countNodesDiGui(root?.left) + (1 << rightN) - 1 + 1
        }
    }
    
    // 统计层级
    func getCeng(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        var troot = root
        var n = 0
        while troot != nil {
            n += 1
            troot = troot?.left
        }
        return n
    }
}
